import pandas as pd
import math
import copy
import csv
import warnings
warnings.filterwarnings('ignore')
class P:
    def __init__(self,data):
        self.data=data
        self.children=[]
    def addchild(self,B):
        self.children.append(B)

def process(data, lables, P0):
        N = len(lables)
        y = []
        for row in data:
            y.append(row[N - 1])
        t = lables[N - 1]
        y_cnt = {}  # 将结果用一个字典存储
        # 统计结果
        for value in y:
            #get(value, num)函数的作用是获取字典中value对应的键值, num=0指示初始值大小。
            y_cnt[value] = y_cnt.get(value, 0) + 1
        y_key = [key for key in y_cnt.keys()]
        y_value = [value for value in y_cnt.values()]
        #print("计算决定属性：\'",t,"\'的信息熵")
        #print(y_cnt)
        info_y = 0
        for v in y_value:
            info_y = info_y - v / len(y) * math.log(v / len(y)) / math.log(2)
        ##print(t,"的信息熵为：",info_y)
        ##print('--------------------')
        if info_y == 0.0:
            ##print('已到达叶子节点',y_key[0])
            P1 = P('THEN:' + y_key[0])
            P0.addchild(P1)
            #("------------------------")
            return

        elif info_y > 0 and len(lables) == 1:

            if info_y != 1.0:
                inde = y_value.index(max(y_value))
            else:
                inde = y_value.index(y_value[0])
            ##print('无可用属性，强制到达叶子节点', y_key[inde])
            P1 = P('THEN:' + y_key[inde])
            P0.addchild(P1)
            ##print("------------------------")
            return

        else:
            Gr = []
            for i in range(N - 1):
                x = [row[i] for row in data]
                ##print(x)
                ##print("属性：\'",lables[i],"\'的信息熵")
                x_cnt = {}  # 将结果用一个字典存储
                for value in x:
                    # get(value, num)函数的作用是获取字典中value对应的键值, num=0指示初始值大小。
                    x_cnt[value] = x_cnt.get(value, 0) + 1
                x_key = [key for key in x_cnt.keys()]
                x_value = [value for value in x_cnt.values()]
                ##print(x_cnt)
                info_x0 = []
                info_x = 0
                for k in range(len(x_key)):
                    x0_cnt = {}
                    info_x0.append(0)
                    #print("计算",lables[i], ":",x_key[k],"的条件熵")
                    for l in y_key:
                        for j in range(len(x)):
                            if x[j] == x_key[k] and y[j] == l:
                                x0_cnt[l] = x0_cnt.get(l, 0) + 1
                    #print(x0_cnt)
                    for v in x0_cnt.values():
                        info_x0[k] = info_x0[k] - v / x_value[k] * math.log(v / x_value[k]) / math.log(2)
                    ##print(lables[i],':',x_key[k],"的条件熵为：",info_x0[k])
                    info_x = info_x + x_value[k] / len(x) * info_x0[k]
                ##print('-----------------')
                ##print(lables[i],"的信息熵为：",info_x)
                Gain = info_y - info_x
                ##print(lables[i],"的信息增益为：",Gain)
                H_x = 0
                for v in x_value:
                    H_x = H_x - v / len(x) * math.log(v / len(x)) / math.log(2)
                ##print(lables[i], "的分裂信息度量为：", H_x)
                if H_x != 0:
                    Gain_ratio = Gain / H_x
                else:
                    Gain_ratio = Gain
                    ##print('-------------------------------------------------------------------------------------')
                ##print(lables[i], "的信息增益率为：", Gain_ratio)
                Gr.append(Gain_ratio)
                ##print('-----------------')
            ##print("各属性信息增益率")
            # for i in range(N - 1):
            ##print(lables[i],Gr[i])
            x_max = max(Gr)
            ind = Gr.index(x_max)
            ##print('信息增益率最大为：',lables[ind])
            #print('选择',lables[ind],'作为子节点')
            ##print('_________________________________')
            leaf = lables[ind]
            leaf_data = [row[ind] for row in data]
            leaf_cnt = {}  # 将结果用一个字典存储
            for value in leaf_data:
                # get(value, num)函数的作用是获取字典中value对应的键值, num=0指示初始值大小。
                leaf_cnt[value] = leaf_cnt.get(value, 0) + 1
            leaf_key = [key for key in leaf_cnt.keys()]
            newlables = copy.copy(lables)
            newlables.remove(leaf)
            #print(newlables)
            for l in leaf_key:
                #print(leaf,'为',l,'时：')
                P1 = P(leaf + ':' + l)
                P0.addchild(P1)
                newdata = []
                for row in data:
                    if len(row) == len(lables):
                        if row[ind] == l:
                            ##print('_____________________________________________________________________________________________')
                            ##print(row)
                            row.pop(ind)
                            ##print(row)
                            newdata.append(row)
                process(newdata, newlables, P1)

def process_main(name):
    path='./data/'+name+".csv"
    data=pd.read_csv(path,'utf-8',engine='python')
    #print(data.shape)
    lables=data.columns.tolist()
    data=data.values.tolist()

    for i in range(len(data)):
        data[i]=data[i][0].split(',')
    data1=copy.deepcopy(data)
    lables=lables[0].split(',')
    #print(len(lables))
    P0=P('Root')

    process(data,lables,P0)

    print("决策树规则为：")
    #print('IF:',end=' ')
    #pre=''
    '''
    def printf(P0):
     if  len(P0.children)!=0:
        for child in range(len(P0.children)):
            ##print(P0.children[child].data, end=' ')
            P1=P0.children[child]
            #printf(P1)
     else:
         ##print('\nIF:',end=' ')
         '''
    #printf(P0)
    ##print('\n')
    #d1, e1, g1, j1, -1, f-1, c1, -1, i1, k-1, h1, b1, a1, 1.0
    sum=0
    correct=0
    #row=['1', '1', '1', '-1', '-1', '-1', '1', '-1', '1', '-1', '1', '1', '1', '1.0']
    #row=['1', '1', '1', '1', '-1', '-1', '1', '-1', '1', '-1', '1', '1', '1', '1.0']
    #row=['-1', '1', '1', '-1', '-1', '-1', '1', '-1', '1', '1', '1', '-1', '1', '3.0']
    for row in data1:
        P1=P0
        #print(row)
        while len(P1.children)!=0:
            n=len(P1.children)
            for i in range(len(P1.children)):
              s = P1.children[i].data
              if 'THEN' in  P1.children[i].data:
                  result=float(P1.children[i].data.split(':')[1])
                  #print(row[-1],result)
                  if result==float(row[-1]):
                      correct=correct+1
                  P1 = P1.children[i]
                  break
              #x3= int(P1.children[i].data.split(':')[0].split("子")[1]) - 1
              #x1 = row[int(P1.children[i].data.split(':')[0].split("子")[1]) - 1]
              #x2 = P1.children[i].data.split(':')[1]
              print(P1.children[i].data.split(':')[0])
              if row[int(P1.children[i].data.split(':')[0].split("子")[1]) - 1]==P1.children[i].data.split(':')[1]:
                  ##print(x1,x2,end='\t')
                  P1=P1.children[i]
                  break
        sum=sum+1
    print(name,'正确率：', correct/sum)
if __name__=='__main__':
    names=['liver','iris','glasss','heart','cleveland']
    #names=['cleveland']
    #names=['heart']
    for name in names:
       #pre.pre(name)
       process_main(name)